package offer;

import java.util.Arrays;

public class _07_重建二叉树 {

    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

    public static void main(String[] args) {
        int[] preorder = {3, 9, 20, 15, 7};
        int[] inorder = {9, 3, 15, 20, 7};
        Solution solution = new _07_重建二叉树().new Solution();
        TreeNode res = solution.buildTree(preorder, inorder);
        System.out.println("调试查看");
    }

    class Solution {
        public TreeNode buildTree(int[] preorder, int[] inorder) {
            int num = preorder[0];
            TreeNode root = new TreeNode(num);
            int index = -1;
            for (int i = 0; i < inorder.length; i++) {
                if (inorder[i] == num) {
                    index = i;
                    break;
                }
            }
            if ((inorder.length > 1) && (index != 0 || index != inorder.length - 1)) {
                int[] leftPre = Arrays.copyOfRange(preorder, 1, 1 + index);
                int[] rightPre = Arrays.copyOfRange(preorder, 1 + index, preorder.length);
                int[] leftIn = Arrays.copyOfRange(inorder, 0, index);
                int[] rightIn = Arrays.copyOfRange(inorder, index + 1, inorder.length);
                if (index != 0) root.left = buildTree(leftPre, leftIn);
                if (index != inorder.length - 1) root.right = buildTree(rightPre, rightIn);
            }
            return root;
        }
    }
}
